package com.banmao.algorithm.No501To700.No617;

public class Solution1 {

    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {

        TreeNode root = recursive(root1, root2);

        return root;

    }

    private TreeNode recursive(TreeNode root1, TreeNode root2) {

        // 这两个if的剪枝，提高了相当程度的效率
        if(root1 == null) {
            return root2;
        }

        if(root2 == null) {
            return root1;
        }

        if(root1 == null && root2 == null) {
            return null;
        }

        TreeNode root = new TreeNode();
        int val = 0;

        if(root1 != null) {
            val += root1.val;
        }
        if(root2 != null) {
            val += root2.val;
        }

        root.val = val;

        root.left = recursive(root1 == null ? null : root1.left, root2 == null ? null : root2.left);
        root.right = recursive(root1 == null ? null : root1.right, root2 == null ? null : root2.right);

        return root;
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
